package java_class;

import com.sun.deploy.util.StringUtils;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * 递归
 */
public class demo001
{
    public static void main(String[] arge){
        // 数组求和
        System.out.println("数组求和：" + sum(0,0,new int[]{1,4,2,3,1,4}));
//        // 汉诺塔问题
//        Stack<String> stackSelf = new Stack<String>();
//        stackSelf.push("A");
//        stackSelf.push("B");
//        stackSelf.push("C");
//        stackSelf.push("D");
//        stackSelf.push("E");
//        stackSelf.push("F");
//        Stack<String> stackTarget = new Stack<String>();
//        System.out.println(StringUtils.join(stackSelf,"--"));
//        hanoi(6, stackSelf, new Stack<>(), stackTarget);
//        System.out.println(StringUtils.join(stackTarget,"--"));
        Scanner imput = new Scanner(System.in);
        char A = 'A';
        char B = 'B';
        char C = 'C';
        System.out.println("******************************************************************************************");
        System.out.println("这是汉诺塔问题（把A塔上编号从小号到大号的圆盘从A塔通过B辅助塔移动到C塔上去");
        System.out.println("******************************************************************************************");
        System.out.print("请输入圆盘的个数：");
        int disks = imput.nextInt();
        TowersOfHanoi.hanoi(disks, A, B, C);
        System.out.println(">>移动了" + TowersOfHanoi.m + "次，把A上的圆盘都移动到了C上");
        imput.close();
    }
    /**
     * 数组求和
     */
    public static int sum(int sum, int index, int[] arr){
        if(sum >= arr.length){
            return sum;
        }
        return sum(sum + arr[index], index +1 ,arr);
    }
//    /**
//     * 汉诺塔问题
//     */
//    public static void hanoi(int n, Stack<String> stackA, Stack<String> stackB, Stack<String> stackC){
//        if(n == 1){//圆盘只有一个时，只需将其从A塔移到C塔
//            hanoi_move(stackA, stackC);//将编b号为1的圆盘从A移到C
//        }else{//否则
//            hanoi(n - 1, stackA, stackB, stackB);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
//            hanoi_move(stackA, stackC);//把A塔上编号为n的圆盘移到C上
//            hanoi(n - 1, stackB, stackA, stackC);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
//        }
//    }
//    public static void hanoi_move(Stack<String> stackSelf, Stack<String> stackTarget){
//        stackTarget.push(stackSelf.pop());
//    }

    public static class TowersOfHanoi {
        static int m =0;//标记移动次数
        //实现移动的函数
        public static void move(int disks,char N,char M) {
            System.out.println("第" + (++m) +" 次移动 : " +" 把 "+ disks+" 号圆盘从 " + N +" 移到  " + M);
        }
        //递归实现汉诺塔的函数
        public static void hanoi(int n, char A, char B, char C) {
            if (n == 1) { //圆盘只有一个时，只需将其从A塔移到C塔
                TowersOfHanoi.move(1, A, C);//将编b号为1的圆盘从A移到C
            } else {//否则
                hanoi(n - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
                TowersOfHanoi.move(n, A, C);//把A塔上编号为n的圆盘移到C上
                hanoi(n - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
            }
        }
    }
}
